\documentclass[10pt,a4paper,onecolumn]{report}
\usepackage[latin1]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{multicol}
\author{Kevin Johnson, Joel Howard}
\title{Lab 1: Potential Fields}
\begin{document}
\maketitle
\begin{multicols}{2}
\section*{Potential Fields}
The idea behind the potential fields lab was to give our tanks simple motivations for their actions. They do not base their actions off of a search of the best actions to take. Rather, they simply know whether they are being attracted towards a location, or pushed away from a location. This concept is modelled effectively through the use of various potential fields. Each field determines the tanks desired trajectory based off of the location of the tank. Once the desired trajectory has been calculated for each field, those vectors are combined to produce the final trajectory for the tank. This allows the tank to seek the enemy flag, while attempting to avoid enemy tanks and scooting around walls.

\subsection*{Attractive Field}
The attractive field takes the location of the goal and the location of the tank. By subtracting the tank location from the goal location we come up with a vector that points directly toward the goal. This vector is then scaled between 0 and 1 to give the tank it's desired speed in that direction. If the magnitude of the attractive vector is greater than some threshold we know that we want to move at full speed. However, once we are within the threshold we want to ensure that we will capture the enemy flag. To accomplish this we scale down our speed in relationship to our proximity to the goal.

Examples of the attractive field can be seen in figures 4 and 5.

\subsection*{Repulse Field}
The repulse field is very similar in concept to the attractive field. However, instead of getting a vector pointing directly at the goal, we obtain the opposite vector to push us away from the danger zone. We found that it was important to gauge how much influence the repulse vectors had, however. If we allowed them to have too much influence our tank would spend much of its time running away from enemy tanks, and would have a difficult time reaching the enemy flag. By reducing the repulse vectors magnitude we were able to pay attention to enemy tanks, without being so afraid of them that we couldn't accomplish our goal of reaching the enemy flag. The following equation shows how we scaled the repulse vectors.
\begin{equation}
s_{r} =
\left\{
	\begin{array}{ll}
		0 & \mbox{if } d > t_{1} \\
		\frac{1}{1 + d} & \mbox{if } t_{1} \leq d \leq t_{2} \\
		1 & \mbox{if } d < t_{2}
	\end{array}
\right.
\end{equation}

Following this equation, we can see that if the distance $d$ of our tank to the enemy tank was greater than some threshold $t_{1}$ we are unaffected by that tanks presence. However, if the distance between our tank and the enemy tank is within $t_{1}$ and $t_{2}$ we move away proportional to the distance between us. If we find ourselves closer than $t_{2}$ we want to move away as fast as we can.

Examples of the repulsive field can be seen in figures 6 and 7.

\subsection*{Tangential Field}
The tangential fields, though simple in concept, were perhaps the most complicated to implement.  Conceptually, the tangential field is comprised of vectors that are tangent to the sides of the object in question.  This, however, is easier said than done.  To be able to calculate the tangential vector of a given position, we first needed to figure out the tangent of the closest side of the object.  Consequently, To figure out the tangent of the closest side we first needed to determine the closest side.

Figuring out the closest side proved to be the brunt of the work.  We used line segment intersection to solve this problem.  By defining an edge of the object as one line segment, then defining the second line segment to be between the center of the object and the tank location, figuring out which side of the object the tank proved to be some simple geometry.  This is well documented on the internet and as such will not be discussed here.  Once we had the closest side, finding the tangent was a simple matter of creating a ray from the endpoints of that side.  Given that the sides of the objects were defined in clockwise order our tangent vectors pointed in the same clockwise order.

The last implementation detail to note is how we scaled the tangent vectors.  Just as with the repulse fields, we do not want tangent fields on the other side of the map affecting how our tank drives.  The following is how we determined our scale factor:
\begin{equation}
s_{t} =
\left\{
	\begin{array}{ll}
		0 & \mbox{if } d > t_{1} \mbox{ or } d_{r} > r \\
		\frac{1}{1 + d} & \mbox{if } t_{1} \leq d \leq t_{2} \\
		1 & \mbox{if } d < t_{2}
	\end{array}
\right.
\end{equation}
where $d_{r}$ is the distance from the tank to to the center of the object, $d$ is the distance to the closest edge, $t_{1}$ is the outer threshold, $t_{2}$ is the inner threshold, and $r$ is the maximum allowed radius from the center of the object.  Figure 1 is a diagram to help visualize some of the afore mentioned variables.
\end{multicols}
\begin{figure*}
	\begin{center}
		\includegraphics[width=50mm]{./Figures/tangent_diagram}
	\end{center}
	\caption{Visual diagram of select variables used to determine tangential vectors}
	\label{diagram}
\end{figure*}
\begin{multicols}{2}
Thus if the tank is within the maximum radius and is within the outer threshold $t_{2}$ it is affected by the tangential field.  Examples of the tangential field can be seen in figures 8 and 9.

\subsection*{Random Field}
When combining attractive, repulsive, and tangential fields it is possible to obtain a vector that is essentially a zero magnitude vector. This is a problem because it gives our tank no motivation to move. To counteract this phenomenon we have introduced a random vector that is added into the final trajectory. This mildly affects the direct trajectory of the tank, but helps in situations when the tank would otherwise get stuck.

An example of the random field can be found in figure 10.

\section*{Tuning Process}
The basic implementation of these different fields gave us results that were generally good. However, we noticed several areas where we could improve our performance if we were to introduce a few tweaks.

\subsection*{Sharper Turning}
One of the biggest areas that we were able to improve upon the basic ideas from this lab was with our ability to turn sharply in order to capture the enemy flag. When our tank is far from the enemy flag we decided not to worry about our turning radius. We felt it was more desirable to maintain the fasted speed possible. However, close to the target flag, we wanted to introduce a method of reducing our speed based off of the difference in our actual angle, and our desired angle. The following equation describes how we were able to scale our speed to get a sharper turning radius.

\begin{equation}
s =
\left\{
	\begin{array}{ll}
		1 & \mbox{if } d > t_{mag} \\
		\frac{1}{2 - v_{t} \cdot v_{d}} & \mbox{if } d \leq t_{mag}
	\end{array}
\right.
\end{equation}

If the distance of the tank to the goal was greater than some threshold $t_{mag}$ we did not adjust our speed. However, if the distance was less than or equal to $t_{mag}$ we scale our speed based on the dot product of the tanks current trajectory and the desired trajectory. So, when the difference in the vectors is large we scale quite heavily, and when the difference is small we scale much less.

\subsection*{Specific Scale Factors for different kinds of fields}
We realized that blindly combining the vectors returned by the different fields would give sub optimal results. We introduced a scaling factor for each different kind of field. The following is how we calculated the final vector:
\begin{equation}
v_{f} = S_{a} * v_{a} + S_{r} * v_{r} + S_{t} * v_{t} + S_{r}*v_{r}
\end{equation}
where $S$ is the scale factor for the specified field vector.  This way we could favour tangential fields more than any other kind of field. This helps us to navigate around objects much quicker than if we were determined to get to the goal regardless of that big wall in front of us.

Figures 11 and 12 are examples of what the combined fields look like.

\subsection*{Messing with the thresholds}
Many of our potential fields use some kind of a threshold to scale the vector. We initially set these thresholds to something that seemed reasonable and spent quite some time modifying them to achieve the desired behaviour. For example, we had initially set our repulse field thresholds to a higher number to greatly discourage our tank from coming close to an enemy. We found that having such high numbers greatly impeded our ability to capture the flag and run it back to our base. By reducing the threshold on the repulse field we were able to give enemy tanks a respectable distance without living in mortal fear that they were on the map at all.

\section*{Battle Results}
Figure 2 outlines the results of our personal tests pitting our dumb and pf agents against each other.  Figure 3 outlines the results of pitting our agents against Eric's and Steve's agents.  The following section outlines our observations of each;

\subsection*{Observations}
While our agent did quite well in our head to head battle against Steve and Eric, we noticed several things about the behaviour of our tank that were quite interesting. One interesting thing we noticed was how our tank would get caught in tangential fields and choose to take the long way around an obstacle. It was almost humerus to watch as our human brains could easily see a shorter path to the goal. We also observed that our strategy for obtaining the flag was easily foiled by a tank that stayed in close proximity to the flag.  This was of course due to the equal weighting of the attractive and repulsive fields, i.e. the repulsive field would trump the attractive.  Because we are not aggressive we never shoot down an enemy tank and continue to keep our distance, essentially keeping us from the flag indefinitely. Our opponents, however, took an aggressive stance and were able to shoot us down a few times.

\subsection*{Time spent}
Joel spent around 20 hours on this project, and Kevin spent around 20 hours on this project.
\end{multicols}

\begin{figure}
	\begin{center}
		\begin{tabular}{| l | l | l |}
			\hline Scenario & Map & Winner \\
			\hline PF vs. Dumb & Four L's &  PF agent\\
			PF vs. 2 dumb & Four L's & PF agent \\
			PF vs. PF & Four L's & Tie \\
			PF vs. Dumb & Rotated Box World &  PF agent\\
			PF vs. 2 dumb & Rotated Box World & PF agent \\
			PF vs. PF & Rotated Box World & Tie \\
			\hline
		\end{tabular}	
	\end{center}	
	\caption{Results for personal tests}
	\label{personal}
\end{figure}

\begin{figure}
	\begin{center}
		\begin{tabular}{| l | l | l | l |}
			\hline Our agents & Their agents & Map & Winner \\
			\hline PF & Dumb & Four L's &  Ours\\
			PF & 2 Dumb & Four L's & Ours \\
			Dumb & PF & Four L's &  Theirs \\
			2 Dumb & PF & Four L's & Theirs \\
			PF & PF & Four L's & Ours \\
			PF & Dumb & Rotated Box World &  Ours\\
			PF & 2 Dumb & Rotated Box World & Ours \\
			Dumb & PF & Rotated Box World &  Tie \\
			2 Dumb & PF & Rotated Box World & Tie \\
			PF & PF & Rotated Box World & Ours \\
			\hline
		\end{tabular}	
	\end{center}	
	\caption{Results for tests against another team}
	\label{personal}
\end{figure}

\begin{figure*}
\includegraphics[width=120mm]{./Figures/Attract.png}
\caption{Attract field of the four\_ls map}
\label{Attract1}
\end{figure*}

\begin{figure*}
\includegraphics[width=120mm]{./Figures/Attract2.png}
\caption{Attract field of the rotated\_box\_world map}
\label{Attract2}
\end{figure*}

\begin{figure*}
\includegraphics[width=120mm]{./Figures/Repulse.png}
\caption{Repulse field of a single enemy tank in the four\_ls map}
\label{Repulse1}
\end{figure*}

\begin{figure*}
\includegraphics[width=120mm]{./Figures/Repulse2.png}
\caption{A close up of the repulse field of a single enemy tank in the rotated\_box\_world map}
\label{Repulse2}
\end{figure*}

\begin{figure*}
\includegraphics[width=120mm]{./Figures/Tangent.png}
\caption{Tangent fields of the four\_ls map}
\label{tanget1}
\end{figure*}

\begin{figure*}
\includegraphics[width=120mm]{./Figures/Tangent2.png}
\caption{Tangent fields of the rotated\_box\_world map}
\label{tangent2}
\end{figure*}

\begin{figure*}
\includegraphics[width=120mm]{./Figures/Random.png}
\caption{Random fields of the four\_ls map}
\label{random}
\end{figure*}

\begin{figure*}
\includegraphics[width=120mm]{./Figures/Combined.png}
\caption{Combined fields of the four\_ls map}
\label{combined1}
\end{figure*}

\begin{figure*}
\includegraphics[width=120mm]{./Figures/Combined2.png}
\caption{Combined fields of the rotated\_box\_world map}
\label{combined2}
\end{figure*}

\end{document}
